This invention relates to synchronous communication networks and, in particular, to the determination of transmission delays between the spatially distributed nodes of such networks.
In a massively parallel processing system, a large number of processing nodes can be interconnected and operated as a single, coherent computing machine.
The switching network in a massively parallel processing system may comprise a multitude of identical integrated-circuit switch elements that are interconnected to provide a high-bandwidth, low-latency, synchronous communication path between any pair of processing nodes. The number of switch elements needed to implement an omega network topology, for example, varies as EQU (N/n)log.sub.n N
where N denotes the number of processing nodes and n is the fan out of the switch element. Thus, for a design in which n=4), the number of switch elements needed for a 16,384-node system is 28,672. And, to further emphasize the size and complexity of these networks, it may be noted that each switch element is generally connected to 2n other switch elements, resulting in a layout and wiring problem of large proportions. Understandably, such networks can be difficult to design, develop and initialize, and they can also make the diagnosis of hardware/software failures a challenging task. Equally understandable, therefore, anything that can be done to reduce this complexity would be advantageous.
Phase multiplexing is the seamless interleaving of different phases of operation. Using phase multiplexing and a distinct service phase, a phase multiplexed communication system is able to service itself dynamically using the same communication facilities provided for run phase, the message transfer phase that supports parallel processing. Thus, by eliminating the need for a completely separate "service" network, phase multiplexing achieves simplification by avoiding additional wiring and the concomitant need for additional connectivity at each switch element, additional complexity that would inevitably increase the cost of the system.
Phase multiplexing is not, however, without a price, and that price is the additional logic needed throughout the network to synchronize phase transitions. It is therefore necessary that this logic be kept to a minimum in order to achieve a favorable trade-off in the use of phase multiplexing rather than a separate service network. A phase multiplexed communication network is described in U.S. patent application Ser. No. 992,200 filed Dec. 17, 1992 by Monty M. Denneau et al entitled "Synchronous Communication System Having Multiplexed Information Transfer and Transition Phases." As described therein, the logical complexity of accommodating the so-called phase-transition problem can be solved by introducing globally executed transition phases, special phases of fixed duration (Q clock cycles) which are effective provided that a parameter called exposure (e) is within the bounded range EQU 0.ltoreq.e.sub.i .ltoreq.Q [1]
for each and every transmission segment (i=0, 1, 2, . . . ) of the network. (A transmission segment is a specifically defined portion of each transmission path between any pair of communicating devices, each such device also being called a channel.)
The above patent application also shows how the pair of equations (1) that govern full-duplex information transfer between two channels over any two oppositely directed segments (collectively called a transmission stage) can be reduced to the single constraint EQU G(0,K-Q).ltoreq.e.ltoreq.L(K,Q) [2]
where e is the exposure at either segment of the stage, K (called stage latency) is a measurable constant associated with the round-trip signal delay through the stage, and G and L denote, respectively, the greater and lesser of the quantities in the associated parenthesis. Thus, in order to achieve full-duplex, transitioned phase-multiplexing on a global basis, Equation (2) must be satisfied by all transmission stages of the network, and this makes exposure a critical parameter relative to the initialization of a phase multiplexed communication system.
For phase multiplexed channels, moreover, it happens that precise values of exposure are also needed for the purpose of setting the counters used for frame synchronization, the so-called slot-out and slot-in counters. This additional dependence upon exposure, combined with that of transitioned phase multiplexing, as expressed by Equation (2), makes exposure determination an inseparable part of phase multiplexed architecture, and additional logic is needed for this purpose. Given the need to keep logical complexity to a minimum, it was therefore necessary to seek innovative ways and means for determining exposure throughout a phase multiplexed network.
The present invention is also applicable to communication networks in general, particularly whenever time or event synchronization is needed. This broad and important general applicability is a consequence of the fact that exposure is synonymous with transmission delay and, in particular, with what is defined herein as virtual transmission delay (vtd).